package org.liaohailong.helloworld.sort;

import java.util.ArrayList;
import java.util.LinkedList;

/**
 * Author: liaohailong
 * Time: 2021/8/2 15:46
 * Describe: 基数排序
 */
public class RadixSort implements ISort {

    @Override
    public void sort(int[] arr) {
        // 创建10个桶
        ArrayList<LinkedList<Integer>> bucket = new ArrayList<>();
        for (int i = 0; i < 10; i++) bucket.add(new LinkedList<>());

        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int i : arr) {
            if (i > max) max = i;
            else if (i < min) min = i;
        }

        // 计算出排序次数
        int count = Math.max(repeat(max), repeat(min));

        // 开始排序
        int repeat = 0;
        while (count-- > 0) {
            // 数据进入桶
            for (int i : arr) {
                int divider = repeat == 0 ? 1 : (int) Math.pow(10, repeat);
                int base = (i / divider) % 10; // 计算出基数

                LinkedList<Integer> list = bucket.get(base);
                list.addLast(i);
            }
            // 从桶中取出，归还给arr
            int pos = 0;
            for (LinkedList<Integer> list : bucket) {
                for (int value : list) {
                    arr[pos] = value;
                    pos++;
                }
                list.clear();
            }
            repeat++;
        }
    }

    private int repeat(int value) {
        int count = 0;
        while (value > 1) {
            count++;
            value /= 10;
        }
        return count;
    }

}
